//定义一个栈入数据，一个栈出数据
typedef int StackDate;
typedef struct Stack {
	StackDate* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* st);
void StackDestory(Stack* st);
void StackPush(Stack* st, StackDate x);
void StackPop(Stack* st);
StackDate StackTop(Stack* st);
bool StackEmpty(Stack* st);
int StackSize(Stack* st);

void StackInit(Stack* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}

void StackDestory(Stack* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = st->capacity = 0;
}
void StackPush(Stack* st, StackDate x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		StackDate* tmp = (StackDate*)realloc(st->a, newcapacity * sizeof(StackDate));
		if (tmp == NULL)
		{
			printf("relloc err\n");
			return;
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top] = x;
	st->top++;
}
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
StackDate StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top-1];
}
bool StackEmpty(Stack* st)
{
	assert(st);
	return st->top == 0;
}
int StackSize(Stack* st)
{
	assert(st);
	return st->top;
}

typedef struct {
    Stack* input;
    Stack* output;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    Stack* input = (Stack*)malloc(sizeof(Stack));
    Stack* output = (Stack*)malloc(sizeof(Stack));
    StackInit(input);
    StackInit(output);
    obj->input = input;
    obj->output = output;
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(obj->input, x);
}
void In_to_Out(MyQueue* obj){
    while(!StackEmpty(obj->input)){
        StackPush(obj->output,StackTop(obj->input));
        StackPop(obj->input);
    }
}
int myQueuePop(MyQueue* obj) {
    //如果出数据的栈为空，就把入数据的栈 弹出再压到出数据栈
    if(StackEmpty(obj->output))
    {
        In_to_Out(obj);
    }
    int top = StackTop(obj->output);
    StackPop(obj->output);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(obj->output))
    {
        In_to_Out(obj);
    }
    int top = StackTop(obj->output);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(obj->input) && StackEmpty(obj->output);
}

void myQueueFree(MyQueue* obj) {
    StackDestory(obj->input);
    StackDestory(obj->output);
    free(obj);
    obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/